package 链表;

public class No2两数相加_链表题 {

    /**
     * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
     *
     * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
     *
     * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     *
     * 示例：
     *
     * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
     * 输出：7 -> 0 -> 8
     * 原因：342 + 465 = 807
     */

    /**
     * 遇到比Long还大的数字会报错,不行
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        StringBuilder sb1=new StringBuilder(getString(l1, ""));
        Long i1 = Long.parseLong(sb1.reverse().toString());
        StringBuilder sb2=new StringBuilder(getString(l2, ""));
        Long i2 = Long.parseLong(sb2.reverse().toString());
        StringBuilder stringBuilder=new StringBuilder(String.valueOf(i1+i2));
        String str=stringBuilder.reverse().toString();
        return stringToNode(str, 0);
    }

    private static String getString(ListNode node,String str){
        if(node==null)
            return "";
        str+=node.val+getString(node.next,str);
        return str;
    }

    private static ListNode stringToNode(String str,Integer index){
        int i = str.charAt(index++)-48;
        ListNode listNode=new ListNode(i);
        if(index==str.length())
            return listNode;//不继续递归了
        listNode.next=stringToNode(str, index);
        return listNode;
    }

    public ListNode addTwoNumbersGood(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        int carry = 0;
        while(l1 != null || l2 != null) {
            //两个链表一起吃进去
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;

            carry = sum / 10;//进位
            sum = sum % 10;//剩余
            cur.next = new ListNode(sum);//放入剩余

            cur = cur.next;//拼接

            //两个一起吃完就共同进下一个
            if(l1 != null)
                l1 = l1.next;
            if(l2 != null)
                l2 = l2.next;
        }
        //最后carry要么为1,要么为0
        if(carry == 1) {
            cur.next = new ListNode(carry);
        }
        return pre.next;
    }

    public static void main(String[] args) {
        ListNode listNode5=new ListNode(5,null);
        ListNode listNode4=new ListNode(4,listNode5);
        ListNode listNode3=new ListNode(3,listNode4);
        ListNode listNode2=new ListNode(2,listNode3);
        ListNode listNode1=new ListNode(1,listNode2);

        ListNode listNode55=new ListNode(50,null);
        ListNode listNode44=new ListNode(20,listNode55);
        ListNode listNode33=new ListNode(30,listNode44);
        ListNode listNode22=new ListNode(20,listNode33);
        ListNode listNode11=new ListNode(10,listNode22);

        ListNode listNode = addTwoNumbers(listNode1, listNode11);

        ListNode cur=listNode;

        while (cur!=null){
            System.out.println(cur.val);
            cur=cur.next;
        }

    }

}
